package demo.lintcode;

import java.util.*;

public class P92_2 {

    public int backPack(int m, int[] A) {

        int max = 0;
        Set<Integer> set = new HashSet<>();
        set.add(0);

        Arrays.sort(A);
        for (int i = 0; i < A.length; i++) {
            List<Integer> c = new ArrayList<>();
            for (Integer su : set) {
                if (su + A[i] <= m) {
                    max = Math.max(su + A[i], max);
                    c.add(su + A[i]);
                }
            }
            set.addAll(c);
        }
        return max;
    }
}
